package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;

//零钱兑换2
/*
    给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。
 */
/*
    给定总金额amount和数组coins。
    dp[x]表示金额之和为x的硬币组合数，目标是求dp[amount]
    dp[0]=1
 */
public class Leetcode518 {
    public int change1(int amount, int[] coins) {
        if(amount==0) {
            return 1;
        }
        return rec(0,coins,amount);
    }

    //暴力
    public int rec(int index,int[] coins,int remainder){
        if(remainder<0){
            return 0;
        }else if(remainder==0){
            return 1;
        }else {
            int count=0;
            for (int i = index; i < coins.length; i++) {
                count+=rec(i,coins,remainder-coins[i]);
            }
            return count;
        }
    }

    //动态规划
    public int change(int amount, int[] coins){
        int[] dp=new int[amount+1];
        dp[0]=1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i]+=dp[i-coin];
                System.out.println(Arrays.toString(dp));
            }
        }
        return dp[amount];
    }


    public static void main(String[] args) {
        int amount = 5;
        int[] coins = new int[]{1, 2, 5};
        int res = new Leetcode518().change(amount, coins);
        System.out.println(res);
    }
}
